1. Field of the Invention
This invention relates to joint pseudo random decision making in a distributed program.
2. Description of Background
A distributed program involves a plurality of processes running concurrently and accessing shared resources. Some distributed programs must make joint decisions. A decision is a choice between several known alternatives and a joint decision is one in which a plurality of processes make the same decision. A decision can be deterministic, e.g., based on an analysis of some shared data. If a decision is deterministic all processes can arrive at the same decision through analysis of the data. Some communication may be required among the processes to enable all of them to base their decision on the same data.
Some distributed programs make decisions that are pseudo random. A pseudo random decision is one that is made based on a set of data, e.g., a sequence of numbers, that approximates the properties of random numbers. A distributed random test generator is an example of a distributed program that makes pseudo random decisions.
Some distributed programs make joint decisions that are pseudo random. Because a joint decision is to be made, the decision must be the same for each process as well as being pseudo random. A distributed random test generator is an example of a distributed program that makes joint pseudo random decisions.
FIG. 1 shows a conventional method for making joint pseudo random decisions. The method shown in FIG. 1 requires that one process 10 is designated as a “monarch” process. The monarch process P1 10 makes each pseudo random decision D1 and communicates the result of the decision to the other processes P2 11, and P3 12, through unidirectional communication lines 20 and 21. The joint pseudo random decision D is equal to the process P1 10 decision D1. Another conventional method of making joint pseudo random decisions involves the various processes communicating with each other to reach a consensus joint pseudo random decision each time a joint pseudo random decision is required.
The conventional methods for making joint pseudo random decisions suffer from the problem that they require communication and synchronization for each pseudo random decision. Distributed programs incur high costs in performance due to such communications. The conventional methods also require some processes that are ready to make and use the decision to delay until communication and synchronization is completed.